leetcode经典例题第八题，将链表以规定形式重新排列。

题目描述

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解题思路

将链表后半部进行反转，同时夹逼遍历即可。

代码提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return;
        }
        
        //1.快慢指针，快指针到链表尾的时候慢指针恰好到链表的中间
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //2.利用中间指针将链表切分为两个链表
        ListNode after = slow.next;
        slow.next = null;
        ListNode pre = null;
        
        //3.将后半部链表反转
        while(after != null){
            ListNode afterNext = after.next;
            after.next = pre;
            pre = after;
            after = afterNext;
        }
        
        //4.分别遍历两个链表即可
        ListNode n1 = head;
        ListNode n2 = pre;
        while(n1 != null && n2 != null){
            ListNode n1Next = n1.next;
            ListNode n2Next = n2.next;
            n1.next = n2;
            n1 = n1Next;
            n2.next = n1;
            n2 = n2Next;
        }
    }
}